package com.gong.suanfa.dijkstra;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/17 0017 9:45
 */
public class Dijkstra {

    public static void main(String[] args) {
        int[][] tu = {{0,-1,10,-1,30,100},
                        {-1,0,5,-1,-1,-1},
                        {-1,-1,0,50,-1,-1},
                        {-1,-1,-1,0,-1,10},
                        {-1,-1,-1,20,0,60},
                        {-1,-1,-1,-1,-1,0}};

        int[] arr = tu[0].clone();
        System.out.println(arr == tu[0]);
        int[] flag = new int[tu.length];
        flag[0] = -1;
        int count = 1;//统计已被选的个数

        while (count < tu.length){
            int index = findMinIndex(arr,flag);//返回当前最小值的下标
            flag[index] = -1;count++;
            flushArr(tu,arr,flag,index);//更新数组
        }

        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static void flushArr(int[][] tu, int[] arr, int[] flag, int index) {
        for (int i = 0; i < arr.length; i++) {
            if (flag[i] != -1){
                if (arr[i] == -1 && tu[index][i] != -1){
                    arr[i] = arr[index] + tu[index][i];
                }else if (tu[index][i] == -1){
                    continue;
                } else {
                    arr[i] = arr[i] > (arr[index]+tu[index][i])?(arr[index]+tu[index][i]):arr[i];
                }
            }
        }
    }

    private static int findMinIndex(int[] arr, int[] flag) {
        int minIndex = 0;
        int i = 0;
        for (i = 0; i < flag.length; i++) {
            if (flag[i] != -1 && arr[i] != -1){
                minIndex = i;
                break;
            }
        }
        for (int j = i; j < arr.length; j++) {
            if (flag[j] != -1 && arr[j] != -1){
                if (arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
        }
        return minIndex;
    }
}
